/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / man / prog / geo.prog

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 0a 55 73 69 6e 67 20 61 | 20 70 65 72 73 69 73 74 |.Using a| persist|
|00000010| 65 6e 74 20 64 69 63 74 | 69 6f 6e 61 72 79 20 28 |ent dict|ionary (|
|00000020| 63 66 2e 7e 73 65 63 74 | 69 6f 6e 7e 34 2e 37 29 |cf.~sect|ion~4.7)|
|00000030| 20 66 6f 72 20 70 6c 61 | 6e 61 72 20 70 6f 69 6e | for pla|nar poin|
|00000040| 74 20 6c 6f 63 61 74 69 | 6f 6e 20 0a 28 73 77 65 |t locati|on .(swe|
|00000050| 65 70 20 6c 69 6e 65 20 | 61 6c 67 6f 72 69 74 68 |ep line |algorith|
|00000060| 6d 29 2e 0a 0a 5c 62 65 | 67 69 6e 67 72 6f 75 70 |m)...\be|gingroup|
|00000070| 0a 5c 70 61 72 73 6b 69 | 70 20 30 70 74 5c 62 61 |.\parski|p 0pt\ba|
|00000080| 73 65 6c 69 6e 65 73 6b | 69 70 20 30 70 74 0a 5c |selinesk|ip 0pt.\|
|00000090| 74 74 20 7b 5c 74 74 5c | 6f 62 65 79 73 70 61 63 |tt {\tt\|obeyspac|
|000000a0| 65 73 5c 67 64 65 66 20 | 7b 5c 68 73 6b 69 70 2e |es\gdef |{\hskip.|
|000000b0| 35 65 6d 7d 7d 20 5c 64 | 65 66 5c 70 61 72 7b 5c |5em}} \d|ef\par{\|
|000000c0| 6c 65 61 76 65 76 6d 6f | 64 65 5c 65 6e 64 67 72 |leavevmo|de\endgr|
|000000d0| 61 66 7d 20 5c 63 61 74 | 63 6f 64 65 60 5c 60 3d |af} \cat|code`\`=|
|000000e0| 5c 61 63 74 69 76 65 0a | 5c 6f 62 65 79 6c 69 6e |\active.|\obeylin|
|000000f0| 65 73 20 5c 74 74 76 65 | 72 62 61 74 69 6d 0a 0a |es \ttve|rbatim..|
|00000100| 23 69 6e 63 6c 75 64 65 | 20 3c 4c 45 44 41 2f 70 |#include| <LEDA/p|
|00000110| 6c 61 6e 65 2e 68 3e 0a | 23 69 6e 63 6c 75 64 65 |lane.h>.|#include|
|00000120| 20 3c 4c 45 44 41 2f 70 | 72 69 6f 2e 68 3e 0a 23 | <LEDA/p|rio.h>.#|
|00000130| 69 6e 63 6c 75 64 65 20 | 3c 4c 45 44 41 2f 73 6f |include |<LEDA/so|
|00000140| 72 74 73 65 71 2e 68 3e | 0a 23 69 6e 63 6c 75 64 |rtseq.h>|.#includ|
|00000150| 65 20 3c 4c 45 44 41 2f | 70 5f 64 69 63 74 69 6f |e <LEDA/|p_dictio|
|00000160| 6e 61 72 79 2e 68 3e 0a | 0a 64 6f 75 62 6c 65 20 |nary.h>.|.double |
|00000170| 58 5f 50 4f 53 3b 20 20 | 2f 2f 20 63 75 72 72 65 |X_POS;  |// curre|
|00000180| 6e 74 20 70 6f 73 69 74 | 69 6f 6e 20 6f 66 20 73 |nt posit|ion of s|
|00000190| 77 65 65 70 20 6c 69 6e | 65 0a 0a 69 6e 74 20 63 |weep lin|e..int c|
|000001a0| 6f 6d 70 61 72 65 28 73 | 65 67 6d 65 6e 74 20 73 |ompare(s|egment s|
|000001b0| 31 2c 73 65 67 6d 65 6e | 74 20 73 32 29 0a 7b 20 |1,segmen|t s2).{ |
|000001c0| 6c 69 6e 65 20 6c 31 28 | 73 31 29 3b 0a 20 20 6c |line l1(|s1);.  l|
|000001d0| 69 6e 65 20 6c 32 28 73 | 32 29 3b 0a 0a 20 20 64 |ine l2(s|2);..  d|
|000001e0| 6f 75 62 6c 65 20 79 31 | 20 3d 20 6c 31 2e 79 5f |ouble y1| = l1.y_|
|000001f0| 70 72 6f 6a 28 58 5f 50 | 4f 53 29 3b 0a 20 20 64 |proj(X_P|OS);.  d|
|00000200| 6f 75 62 6c 65 20 79 32 | 20 3d 20 6c 32 2e 79 5f |ouble y2| = l2.y_|
|00000210| 70 72 6f 6a 28 58 5f 50 | 4f 53 29 3b 0a 0a 20 20 |proj(X_P|OS);..  |
|00000220| 72 65 74 75 72 6e 20 63 | 6f 6d 70 61 72 65 28 79 |return c|ompare(y|
|00000230| 31 2c 79 32 29 3b 0a 7d | 0a 0a 0a 74 79 70 65 64 |1,y2);.}|...typed|
|00000240| 65 66 20 70 72 69 6f 72 | 69 74 79 5f 71 75 65 75 |ef prior|ity_queu|
|00000250| 65 3c 73 65 67 6d 65 6e | 74 2c 70 6f 69 6e 74 3e |e<segmen|t,point>|
|00000260| 20 58 5f 73 74 72 75 63 | 74 75 72 65 3b 0a 74 79 | X_struc|ture;.ty|
|00000270| 70 65 64 65 66 20 70 5f | 64 69 63 74 69 6f 6e 61 |pedef p_|dictiona|
|00000280| 72 79 3c 73 65 67 6d 65 | 6e 74 2c 69 6e 74 3e 20 |ry<segme|nt,int> |
|00000290| 20 20 20 20 59 5f 73 74 | 72 75 63 74 75 72 65 3b |    Y_st|ructure;|
|000002a0| 20 0a 0a 73 6f 72 74 73 | 65 71 3c 64 6f 75 62 6c | ..sorts|eq<doubl|
|000002b0| 65 2c 59 5f 73 74 72 75 | 63 74 75 72 65 3e 20 20 |e,Y_stru|cture>  |
|000002c0| 48 49 53 54 4f 52 59 3b | 0a 0a 76 6f 69 64 20 53 |HISTORY;|..void S|
|000002d0| 57 45 45 50 28 6c 69 73 | 74 3c 73 65 67 6d 65 6e |WEEP(lis|t<segmen|
|000002e0| 74 3e 26 20 4c 29 0a 7b | 20 2f 2f 20 50 72 65 63 |t>& L).{| // Prec|
|000002f0| 6f 6e 64 69 74 69 6f 6e | 3a 20 4c 20 69 73 20 61 |ondition|: L is a|
|00000300| 20 6c 69 73 74 20 6f 66 | 20 6e 6f 6e 2d 69 6e 74 | list of| non-int|
|00000310| 65 72 73 65 63 74 69 6e | 67 0a 20 20 2f 2f 20 66 |ersectin|g.  // f|
|00000320| 72 6f 6d 20 6c 65 66 74 | 20 74 6f 20 72 69 67 68 |rom left| to righ|
|00000330| 74 20 64 69 72 65 63 74 | 65 64 20 6c 69 6e 65 20 |t direct|ed line |
|00000340| 73 65 67 6d 65 6e 74 73 | 20 0a 0a 20 20 58 5f 73 |segments| ..  X_s|
|00000350| 74 72 75 63 74 75 72 65 | 20 20 20 20 58 3b 0a 20 |tructure|    X;. |
|00000360| 20 59 5f 73 74 72 75 63 | 74 75 72 65 20 20 20 20 | Y_struc|ture    |
|00000370| 59 3b 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 |Y;      |     .  |
|00000380| 73 65 67 6d 65 6e 74 20 | 20 20 20 20 20 20 20 73 |segment |       s|
|00000390| 3b 0a 0a 20 20 66 6f 72 | 61 6c 6c 28 73 2c 4c 29 |;..  for|all(s,L)|
|000003a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000003b0| 20 20 20 2f 2f 20 69 6e | 69 74 69 61 6c 69 7a 65 |   // in|itialize|
|000003c0| 20 74 68 65 20 58 5f 73 | 74 72 75 63 74 75 72 65 | the X_s|tructure|
|000003d0| 0a 20 20 7b 20 58 2e 69 | 6e 73 65 72 74 28 73 2c |.  { X.i|nsert(s,|
|000003e0| 73 2e 73 74 61 72 74 28 | 29 29 3b 0a 20 20 20 20 |s.start(|));.    |
|000003f0| 58 2e 69 6e 73 65 72 74 | 28 73 2c 73 2e 65 6e 64 |X.insert|(s,s.end|
|00000400| 28 29 29 3b 0a 20 20 20 | 7d 0a 0a 20 20 48 49 53 |());.   |}..  HIS|
|00000410| 54 4f 52 59 2e 69 6e 73 | 65 72 74 28 2d 4d 41 58 |TORY.ins|ert(-MAX|
|00000420| 44 4f 55 42 4c 45 2c 59 | 29 3b 20 2f 2f 20 69 6e |DOUBLE,Y|); // in|
|00000430| 73 65 72 74 20 65 6d 70 | 74 79 20 59 5f 73 74 72 |sert emp|ty Y_str|
|00000440| 75 63 74 75 72 65 20 61 | 74 20 2d 69 6e 66 69 6e |ucture a|t -infin|
|00000450| 69 74 79 0a 0a 20 20 77 | 68 69 6c 65 28 20 21 20 |ity..  w|hile( ! |
|00000460| 58 2e 65 6d 70 74 79 28 | 29 20 29 0a 20 20 7b 20 |X.empty(|) ).  { |
|00000470| 70 6f 69 6e 74 20 20 20 | 70 3b 20 0a 20 20 20 20 |point   |p; .    |
|00000480| 73 65 67 6d 65 6e 74 20 | 73 3b 0a 0a 20 20 20 20 |segment |s;..    |
|00000490| 58 2e 64 65 6c 5f 6d 69 | 6e 28 73 2c 70 29 3b 20 |X.del_mi|n(s,p); |
|000004a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2f 20 6e |        |    // n|
|000004b0| 65 78 74 20 65 76 65 6e | 74 3a 20 65 6e 64 70 6f |ext even|t: endpo|
|000004c0| 69 6e 74 20 70 20 6f 66 | 20 73 65 67 6d 65 6e 74 |int p of| segment|
|000004d0| 20 73 0a 0a 20 20 20 20 | 58 5f 50 4f 53 20 3d 20 | s..    |X_POS = |
|000004e0| 70 2e 78 63 6f 6f 72 64 | 28 29 3b 0a 0a 20 20 20 |p.xcoord|();..   |
|000004f0| 20 69 66 20 28 73 2e 73 | 74 61 72 74 28 29 3d 3d | if (s.s|tart()==|
|00000500| 70 29 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a |p)      |       .|
|00000510| 20 20 20 20 20 20 20 20 | 59 20 3d 20 59 2e 69 6e |        |Y = Y.in|
|00000520| 73 65 72 74 28 73 2c 30 | 29 3b 20 20 20 20 20 20 |sert(s,0|);      |
|00000530| 2f 2f 20 70 20 69 73 20 | 6c 65 66 74 20 65 6e 64 |// p is |left end|
|00000540| 20 6f 66 20 73 20 0a 20 | 20 20 20 65 6c 73 65 0a | of s . |   else.|
|00000550| 20 20 20 20 20 20 20 20 | 59 20 3d 20 59 2e 64 65 |        |Y = Y.de|
|00000560| 6c 28 73 29 3b 20 20 20 | 20 20 20 20 20 20 20 20 |l(s);   |        |
|00000570| 2f 2f 20 70 20 69 73 20 | 72 69 67 68 74 20 65 6e |// p is |right en|
|00000580| 64 20 6f 66 20 73 0a 0a | 20 20 20 20 48 49 53 54 |d of s..|    HIST|
|00000590| 4f 52 59 2e 69 6e 73 65 | 72 74 28 58 5f 50 4f 53 |ORY.inse|rt(X_POS|
|000005a0| 2c 59 29 3b 20 20 20 20 | 2f 2f 20 69 6e 73 65 72 |,Y);    |// inser|
|000005b0| 74 20 59 20 69 6e 74 6f | 20 68 69 73 74 6f 72 79 |t Y into| history|
|000005c0| 20 73 65 71 75 65 6e 63 | 65 20 0a 20 20 7d 0a 0a | sequenc|e .  }..|
|000005d0| 20 20 48 49 53 54 4f 52 | 59 2e 69 6e 73 65 72 74 |  HISTOR|Y.insert|
|000005e0| 28 4d 41 58 44 4f 55 42 | 4c 45 2c 59 29 3b 20 20 |(MAXDOUB|LE,Y);  |
|000005f0| 2f 2f 20 69 6e 73 65 72 | 74 20 65 6d 70 74 79 20 |// inser|t empty |
|00000600| 59 5f 73 74 72 75 63 74 | 75 72 65 20 61 74 20 2b |Y_struct|ure at +|
|00000610| 69 6e 66 69 6e 69 74 79 | 0a 7d 0a 0a 0a 0a 73 65 |infinity|.}....se|
|00000620| 67 6d 65 6e 74 20 4c 4f | 43 41 54 45 28 70 6f 69 |gment LO|CATE(poi|
|00000630| 6e 74 20 70 29 0a 7b 20 | 58 5f 50 4f 53 20 3d 20 |nt p).{ |X_POS = |
|00000640| 70 2e 78 63 6f 6f 72 64 | 28 29 3b 0a 0a 20 20 59 |p.xcoord|();..  Y|
|00000650| 5f 73 74 72 75 63 74 75 | 72 65 20 59 20 3d 20 48 |_structu|re Y = H|
|00000660| 49 53 54 4f 52 59 2e 69 | 6e 66 28 48 49 53 54 4f |ISTORY.i|nf(HISTO|
|00000670| 52 59 2e 70 72 65 64 28 | 58 5f 50 4f 53 29 29 3b |RY.pred(|X_POS));|
|00000680| 0a 0a 20 20 70 5f 64 69 | 63 5f 69 74 65 6d 20 70 |..  p_di|c_item p|
|00000690| 69 74 20 3d 20 59 2e 73 | 75 63 63 28 73 65 67 6d |it = Y.s|ucc(segm|
|000006a0| 65 6e 74 28 70 2c 30 2c | 31 29 29 3b 0a 0a 20 20 |ent(p,0,|1));..  |
|000006b0| 69 66 20 28 70 69 74 20 | 21 3d 20 6e 69 6c 29 20 |if (pit |!= nil) |
|000006c0| 0a 20 20 20 20 20 72 65 | 74 75 72 6e 20 59 2e 6b |.     re|turn Y.k|
|000006d0| 65 79 28 70 69 74 29 3b | 0a 20 20 65 6c 73 65 0a |ey(pit);|.  else.|
|000006e0| 20 20 20 20 20 72 65 74 | 75 72 6e 20 73 65 67 6d |     ret|urn segm|
|000006f0| 65 6e 74 28 30 29 3b 0a | 7d 0a 0a 5c 65 6e 64 67 |ent(0);.|}..\endg|
|00000700| 72 6f 75 70 0a 0a       |                         |roup..  |        |
+--------+-------------------------+-------------------------+--------+--------+